#include "myTree2.h"
#include <bits/stdc++.h>
string pre;  // 保留前序遍历结果
string ino;  // 保留中序遍历结果
string post; // 保留后序遍历结果相反结果即根，右，左
TreeNode *nownode = new TreeNode;
TreeNode *Node = new TreeNode;
using namespace std;
TreeNode::TreeNode(char ch, TreeNode *Lc, TreeNode *Rc, NodeTag LT, NodeTag RT)
{
    this->data = ch;
    this->leftChild = Lc;
    this->rightChild = Rc;
    this->lTag = LT;
    this->rTag = RT;
}
TreeNode::TreeNode()
{
    new (this) TreeNode('\0', NULL, NULL, Link, Link);//问题6：没有空构造函数影响了线索化的Tag初始，其初始状态未设置成Link
}
//问题7：以后不要在用C语言的malloc函数，这个无法调用构造函数来初始化你的线索Tag，这也是为什么之前会出现乱码地址。
TreeNode::~TreeNode() {}
MyTree::MyTree() // 无参构造
{
    this->isThread = 0; // 初始化一颗空树，使他的线索二叉树标志为零
}
MyTree::MyTree(const char ch[]) // 构造函数，根据二叉树的先序序列，生成二叉树的二叉链表存储,使用@表示NULL
{
    //记录ch数组方便复制调用
    int j = 0;
    for (j = 0; ch[j] != 0; j++)
    {
        this->ch[j] = ch[j];
    }
    this->ch[j] = 0;
    stack<TreeNode *> s; // 运用栈记录前序遍历的左节点，方便去根据结点指向右节点
    this->isThread = 0;  //????
    int i = 0;
    if (ch[i] == '@')
        return;
    TreeNode *p;
    TreeNode *q;
    p = new TreeNode;
    this->root = p;
    p->data = ch[i];
    i++;
    while ((ch[i] != '\0') || (!s.empty()))
    {
        if (p == NULL) // p的值为空则读取下一个数值
        {
            i++;
        }
        else // 不断建立左子树，直到遇到“@”即空值
        {
            while (ch[i] != '@')
            {
                q = new TreeNode;
                q->data = ch[i];
                p->leftChild = q;
                s.push(p); // 将遍历过的父结点记录在栈中
                p = q;
                i++;
            }
            p->leftChild = NULL;
            s.push(p);
            i++;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop(); // 读取栈顶元素，去建立右子树，再以其为根节点去建立树
            if (ch[i] != '@')
            {
                q = new TreeNode;
                q->data = ch[i];
                p->rightChild = q;
                p = q; // p=p->rightChild;
                i++;
            }
            else
            {
                p->rightChild = NULL;
                p = NULL; //????
            }
        }
    }
}
/*MyTree::MyTree(const MyTree &T) // 拷贝函数  //问题2：拷贝函数仍旧不对
问题根源我实在是找不到，因为我不太清楚这个的原理到底是怎么复制的，是通过对应位置的遍历？感觉有一点
奇怪，因为我觉得这样无法确定什么地方是空树。所以我对你这里不做改动，我给你注释起来并且重新写了一个好理解的也更方便的
，如果你想自己再找找也可以接着你的思路对应找找问题。
{
    this->isThread = 0; // 该函数同样适合线索二叉树s
    stack<TreeNode *> s1, s2;
    TreeNode *q1;
    q1 = new TreeNode;
    TreeNode *q2; // q2的作用是一块空间，不断复制T树中的值，连接到q1上
    TreeNode *p;
    p = T.root;      // 用p去遍历树节点
    this->root = q1; // 将树复制到q1中
    q1->data = p->data;
    while (p != NULL || !s1.empty())
    {
        while (p != NULL)
        {
            s1.push(p);
            s2.push(q1);
            p = p->leftChild;
            if (p != NULL)
            {

                q2 = new TreeNode;
                q2->data = p->data;
                q1->leftChild = q2;
                q1 = q2;
            }
            else
            {
                q1->leftChild = NULL;
            }
            if (!s1.empty())
            {
                p = s1.top();
                q1 = s2.top();
                s1.pop();
                s2.pop();
                // p=p->rightChild;//有改动
                if (p->rightChild != NULL)
                {
                    q2 = new TreeNode;
                    q1->rightChild = q2;
                    p = p->rightChild;
                    q2->data = p->data;
                    q1 = q2;
                }
                else
                {
                    q1->rightChild = NULL;
                    p = NULL;
                }
            }
        }
    }
}*/
MyTree::MyTree(const MyTree &T)//这种拷贝方法需要你记录下来之前的ch数组，我写到了.h里面。
{
    new(this)MyTree(T.ch);
    //相当于完全复制了你的上一个构造函数MyTree::MyTree(const char[])的代码，等价于这么写：
    /*
    stack<TreeNode *> s; // 运用栈记录前序遍历的左节点，方便去根据结点指向右节点
    this->isThread = 0;  //????
    int i = 0;
    if (T.ch[i] == '@')
        return;
    TreeNode *p;
    TreeNode *q;
    p = new TreeNode;
    this->root = p;
    p->data = T.ch[i];
    i++;
    while ((T.ch[i] != '\0') || (!s.empty()))
    {
        if (p == NULL) // p的值为空则读取下一个数值
        {
            i++;
        }
        else // 不断建立左子树，直到遇到“@”即空值
        {
            while (T.ch[i] != '@')
            {
                q = new TreeNode;
                q->data = T.ch[i];
                p->leftChild = q;
                s.push(p); // 将遍历过的父结点记录在栈中
                p = q;
                i++;
            }
            p->leftChild = NULL;
            s.push(p);
            i++;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop(); // 读取栈顶元素，去建立右子树，再以其为根节点去建立树
            if (T.ch[i] != '@')
            {
                q = new TreeNode;
                q->data = T.ch[i];
                p->rightChild = q;
                p = q; // p=p->rightChild;
                i++;
            }
            else
            {
                p->rightChild = NULL;
                p = NULL; //????
            }
        }
    }
    */
   //上面的是不是更省力而且不会错
}
MyTree::~MyTree() {}            // 析构函数
void MyTree::preOrderTraverse() // 前序遍历
{
    string pre = "\0"; // 保留前序遍历结果
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            pre += p->data;
            cout << p->data;
            s.push(p);
            p = p->leftChild;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rightChild;
        }
    }
}
void MyTree::inOrderTraverse() // 中序遍历
{
    string ino = "\0"; // 保留中序遍历结果
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            s.push(p);
            p = p->leftChild;
        }
        if (!s.empty())
        {
            p = s.top();
            ino += p->data;
            cout << p->data;
            s.pop();
            p = p->rightChild;
        }
    }
}
void MyTree::postOrderTraverse() // 后序遍历
{
    string post = "\0"; // 保留后序相反遍历结果
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            post += p->data;
            s.push(p);
            p = p->rightChild;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->leftChild;
        }
    }
    int len = post.size();
    for (int j = len - 1; j >= 0; j--)
    {
        cout << post[j];
    }
}
int MyTree::countLeaf() // 叶结点计数
{
    int sum = 0;
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            s.push(p);
            p = p->leftChild;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            if ((p->leftChild == NULL) && (p->rightChild == NULL))
                sum++;
            p = p->rightChild; // 不能有else，如果有else会将p点再次入栈
        }
    }
    return sum;
}
int MyTree::height(const TreeNode *root)
{
    int m, n;
    if (root == NULL)
        return 0;
    else
    {
        m = height(root->leftChild);  // 左子树高度
        n = height(root->rightChild); // 右子树高度
    }
    return (m > n) ? m + 1 : n + 1; // 取高的加1
}
int MyTree::countHeight() // 计算树的深度
{
    return height(root);
}
bool MyTree::isThreadedTree() // 判断是否为线索二叉树
{
    return isThread;
}
/*void MyTree::inThread(TreeNode *root)
{
    TreeNode *rec=NULL;//前驱
    TreeNode *p=root;
    if(p==NULL) return;
    if(p!=NULL)
    {
        inThread(p->leftChild);//递归左子树线索化
        if(p->leftChild==NULL)//
        {
            p->lTag=Thread;//前驱线索
            p->leftChild=rec;//左孩子指针指向前驱
        }
        if(rec->rightChild==NULL&&rec!=NULL)//没有右孩子
        {
            rec->rTag=Thread;//后继线索
            rec->rightChild=p;//前驱右孩子指针指向后继（当前节点p）
        }
        rec=p;
        inThread(p->rightChild);//递归右子树线索化
    }
}
bool MyTree::inOrderThreading()    //线索化
{
    isThread=1;
    inThread(root);
}*/
void MyTree::inThread(TreeNode *p,TreeNode **recs)
{
    //TreeNode *rec = NULL; // 前驱
    //问题4：书上这个函数里面哪有rec的定义？它是从你的上一个函数InorderThreading()传下来的rec！
    TreeNode **rec=recs;
    //TreeNode *p = T;//问题7：这样会导致p的数据修改无法传入递归函数，导致你的线索化结果丢失
    if (p != NULL)
    {
        inThread(p->leftChild,rec);   // 递归左子树线索化
        if (p->leftChild == NULL) //
        {
            p->lTag = Thread;   // 前驱线索
            p->leftChild = *rec; // 左孩子指针指向前驱
        }
        if ((*rec)->rightChild == NULL) // 没有右孩子
        {
            (*rec)->rTag = Thread;  // 后继线索
            (*rec)->rightChild = p; // 前驱右孩子指针指向后继（当前节点p）
        }
        *rec = p;
        inThread(p->rightChild,rec); // 递归右子树线索化
    }
}
bool MyTree::inOrderThreading() // 线索化
{
    isThread = 1;
    TreeNode *thrt = new TreeNode;
    TreeNode **rec = new TreeNode*;
    thrt->lTag = Link;
    thrt->rTag = Thread;
    thrt->rightChild = thrt;
    if (root == NULL)//问题3：书上的!T指的是root==NULL，(!T)表示的是T地址不存在（即为NULL）
        thrt->leftChild = thrt;
    else
    {
        thrt->leftChild = root;
        *rec = thrt;//问题4：这个rec要传入到下面这个函数里面，所以要在这个基础上做一定修改
        inThread(this->root,rec);
        (*rec)->rTag = Thread;
        (*rec)->rightChild = thrt;
        thrt->rightChild = *rec;
    }
    return true;
}
TreeNode &MyTree::locateNode(const char &v) // 结点定位
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            if (p->data == v) // 第一个问题，等号没有处理
            {
                return *p;
            }
            s.push(p);
            if (p->lTag == Thread)
            {
                p = NULL;
                break;
            }
            p = p->leftChild; //???
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            if (p->rTag == Thread)
                p = NULL;
            else
                p = p->rightChild;
            // p=p->rightChild;//???
        }
    }
    
}

/*
TreeNode &MyTree::preNode(const TreeNode &v) // 获取前驱结点
{
    int i = ino.find(v.data);
    Node->data = ino[i - 1];
    return *Node;
}
TreeNode &MyTree::nextNode(const TreeNode &v) // 获取后继结点
{
    int i = ino.find(v.data);
    Node->data = ino[i + 1];
    return *Node;
}
*/


//问题8：拜托宝贝儿，前驱后继不是让你这么偷懒的啊······
//https://www.cnblogs.com/jev-0987/p/13202166.html#:~:text=%E5%9C%A8%E4%B8%AD%E5%BA%8F%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E6%89%BE%E5%88%B0%E6%8C%87%E5%AE%9A%E7%BB%93%E7%82%B9%2Ap%E7%9A%84%E4%B8%AD%E5%BA%8F%E5%89%8D%E9%A9%B1pre%20%E8%8B%A5p-%3Eltag%3D%3D1%EF%BC%88%E8%A2%AB%E7%BA%BF%E7%B4%A2%E5%8C%96%E4%BA%86%EF%BC%89%EF%BC%8C%E5%88%99,pre%3Dp-%3Elchild%EF%BC%88%E7%9B%B4%E6%8E%A5%E5%B0%B1%E6%98%AF%E5%89%8D%E9%A9%B1%EF%BC%89%20%E8%8B%A5p-%3Eltag%3D%3D0%EF%BC%88%E6%B2%A1%E6%9C%89%E8%A2%AB%E7%BA%BF%E7%B4%A2%E5%8C%96%EF%BC%89%EF%BC%8C%20%E5%BF%85%E5%AE%9A%E6%98%AF%E6%9C%89%E5%B7%A6%E5%AD%A9%E5%AD%90%E7%9A%84%E3%80%82


TreeNode *Lastnode(TreeNode *p)
{
    //循环找到最右下的结点（不一定是叶子结点）
    while(p->rTag == Link) p=p->rightChild;
    return p;
}

TreeNode *Firstnode(TreeNode *p)
{
    //循环找到最左下角结点（不一定是叶子结点）
    while(p->lTag==Link) p=p->leftChild;
    return p;
}

TreeNode &MyTree::preNode(const TreeNode &T)
{
    if(T.lTag==Thread)return *T.leftChild;
    return *Lastnode(T.leftChild);
}

TreeNode &MyTree::nextNode(const TreeNode &T)
{
   if(T.rTag==Thread)return *T.rightChild;
   return *Firstnode(T.rightChild);
}
void TreeNode::printNode()
{
    cout << this->data;
}
HuffmanTree::HuffmanTree(const int &x, const int ch[]) // 构造函数
{
    n = x;
    m = 2 * n - 1;
    for (int i = 0; i < n; i++)
        t[i].w = ch[i];
    for (int i = 0; i < m; i++)
    {
        t[i].parent = -1;
        t[i].left = -1;
        t[i].right = -1;
    }
    int INF = 0x3f3f3f3f;
    int min1, min2, pos1, pos2;
    for (int i = n; i < m; i++)
    {
        min2 = min1 = INF;
        for (int j = 0; j < i; j++)
        {
            if (t[j].parent == -1)
            {
                if (t[j].w < min1)
                {
                    pos2 = pos1;
                    min2 = min1;
                    pos1 = j;
                    min1 = t[j].w;
                }
                else
                {
                    if (t[j].w < min2)
                    {
                        pos2 = j;
                        min2 = t[j].w;
                    }
                }
            }
        }
        t[i].left = pos1;
        t[i].right = pos2;
        t[i].w = t[pos1].w + t[pos2].w;
        t[pos1].parent = i;
        t[pos2].parent = i;
    }
}

// 析构函数
HuffmanTree::~HuffmanTree() {}
// 按编码输出
void HuffmanTree::printHuffmanCodes()
{
    int maxn = 0, pos = 0;
    for (int i = 1; i <= n; i++)
    {
        maxn = 0;
        for (int j = 0; j < n; j++)
        {
            if (t[j].w > maxn)
            {
                maxn = t[j].w;
                pos = j;
            }
        }
        t[pos].w = -1;
        int pos1;
        string s;
        while (t[pos].parent != -1)
        {
            pos1 = t[pos].parent;
            if (t[pos1].left == pos)
                s = '0' + s;
            else
                s = '1' + s;
            pos = pos1;
        }
        cout << maxn << ":" << s << endl;
    }
    return;
}
int main()
{
    // 树的构造
    MyTree t1("ABDG@@HJ@@K@@@CE@@F@I@@");

    // 前序遍历
    t1.preOrderTraverse(); // ABDGHJKCEFI
    cout << endl;

    // 中序遍历
    t1.inOrderTraverse(); // GDJHKBAECFI
    cout << endl;

    // 后序遍历
    t1.postOrderTraverse(); // GJKHDBEIFCA
    cout << endl;

    // 叶子节点个数
    cout << t1.countLeaf() << endl; // 5

    // 深度
    cout << t1.countHeight() << endl; // 5

    // 寻找树中节点
    TreeNode n1 = t1.locateNode('I');
    n1.printNode(); // I
    cout << endl;

    // 树的构造
    MyTree t2("ABC@D@E@@@@");

    // 前序遍历
    t2.preOrderTraverse(); // ABCDE
    cout << endl;

    // 中序遍历
    t2.inOrderTraverse(); // CDEBA
    cout << endl;

    // 后序遍历
    t2.postOrderTraverse(); // EDCBA
    cout << endl;

    // 叶子节点个数
    cout << t2.countLeaf() << endl; // 1

    // 深度
    cout << t2.countHeight() << endl; // 5

    // 线索化树
    MyTree t3(t1);
    t3.inOrderThreading();
    cout << t2.isThreadedTree() << endl; // 0
    cout << t3.isThreadedTree() << endl; // 1

    // 线索化树寻找前后结点
    TreeNode n2 = t3.locateNode('A');
    TreeNode n3 = t3.preNode(n2);
    TreeNode n4 = t3.nextNode(n2);

    n3.printNode(); // B
    cout << endl;
    n4.printNode(); // E
    cout << endl;

    TreeNode n5 = t3.locateNode('K');
    TreeNode n6 = t3.preNode(t3.preNode(n5));
    // 提示：若此处跨头结点会发生什么？

    n6.printNode(); // J
    cout << endl;

    // 霍夫曼树
    int nodes[6] = {3, 7, 30, 1, 16};
    HuffmanTree t4(5, nodes);
    t4.printHuffmanCodes();

    /*
        30:1
        16:01
        7:001
        3:0001
        1:0000
    */
    system("pause");
    return 0;
}